package com.mccken.practice.top100.Top_1$20.top_1;

import java.util.HashMap;

/**
 * 两数之和
 * https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-28 09:50
 **/
public class TowSum {

	/**
	 * 查表法
	 * 
	 * 时间复杂度 O(n)  n为数组长度
	 * 空间复杂度 O(n)  哈希表里最多存 n-1个键值对
	 */ 
	public int[] twoSum(int[] nums, int target) {
		HashMap<Integer, Integer> map = new HashMap<>();
		map.put(nums[0], 0);
		
		int length = nums.length;
		for (int i = 1; i < length; i++) {
			if (map.containsKey(target - nums[i])) {
				Integer j = map.get(target - nums[i]);
				return new int[]{i, j};
			}
			map.put(nums[i], i);
		}
		return null;
	}

	/**
	 * 暴力破解法
	 * 
	 * 时间复杂度： O(n^2)  N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
	 * 空间复杂度： O(1)
	 */
	public int[] twoSum2(int[] nums, int target) {
		for (int i = 0; i < nums.length - 1; i++) {
			for (int j = i+1; j < nums.length; j++) {
				if (target == nums[i] + nums[j]) {
					return new int[]{i,j}; 	
				}
			}	
		}
		return null;
	}
}
